package Leetcode.树;

/**
 * @ClassName 二叉树的最近公共祖先
 * @since: 2023/8/19 11:53
 * @auth: kirito
 * @description:
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
 * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大
 * （一个节点也可以是它自己的祖先）。”
 **/
public class 二叉搜索树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int x = root.val;
        if (p.val < x && q.val < x) {
            // p和q都小于当前节点的值，说明最近公共祖先在当前节点的左子树中
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > x && q.val > x) {
            // p和q都大于当前节点的值，说明最近公共祖先在当前节点的右子树中
            return lowestCommonAncestor(root.right, p, q);
        }
        // 如果p和q分别位于当前节点的左右子树中，或者其中一个节点的值等于当前节点的值，当前节点即为最近公共祖先
        return root;
    }
}
